package universe;

import java.util.LinkedList;

import universe.unit.Coordinated;

public class IntQuadTree {
	
	int maxX, maxY, minX, minY;
	private IntQuadTree[] children;
	Coordinated o;
	
	public IntQuadTree(){
		children= new IntQuadTree[4];
		maxX= Integer.MAX_VALUE;
		maxY= maxX;
		minX= Integer.MIN_VALUE;
		minY= minX;
		o=null;
	}
	
	public IntQuadTree(int maxX, int maxY, int minX, int minY){
		children= new IntQuadTree[4];
		this.maxX= maxX;
		this.maxY= maxY;
		this.minX= minX;
		this.minY= minY;
		o=null;
	}
	public boolean isEmpty(){
		boolean empty= this.o==null;
		for(int i=0; i<4 && empty; i++){
			empty= empty && children[i]==null;
		}
		return empty;	
	}
	
	public boolean isEmpty(int x, int y){
		IntQuadTree currentTree= this;
		while(currentTree.o == null){
			int midX= (currentTree.maxX-currentTree.minX)/2 + currentTree.minX;
			int midY= (currentTree.maxY-minY)/2 + currentTree.minY;
			if(x> midX){
				if(y> midY){
					currentTree= currentTree.children[0];
				}else{
					currentTree= currentTree.children[3];
				}
			}else{
				if(y> midY){
					currentTree= currentTree.children[1];
				}else{
					currentTree= currentTree.children[2];
				}
			}
			if(currentTree==null){
				return false;
			}
		}
		int[] coord= currentTree.o.getCoord();
		
		return coord[0]==x && coord[1]==y;
	}
	
	public boolean put(int x, int y, Coordinated c){
		// This is a superfluous call to isEmpty. The check could be merged with the rest of the traversal
		// possible speed optimization (if necessary)
		if(!isEmpty(x,y)){
			return false;
		}
		IntQuadTree currentTree= this;
		while(currentTree.o == null){
			if( currentTree.isEmpty()){
				currentTree.o=c;
				break;
			}
			
			int midX= (currentTree.maxX-currentTree.minX)/2 + currentTree.minX;
			int midY= (currentTree.maxY-minY)/2 + currentTree.minY;
			if(x> midX){
				if(y> midY){
					if(currentTree.children[0] == null){
						currentTree.children[0]= new IntQuadTree(currentTree.maxX, currentTree.maxY, midX+1, midY+1);
					}
					currentTree= currentTree.children[0];
				}else{
					if(currentTree.children[3] == null){
						currentTree.children[3]= new IntQuadTree(currentTree.maxX, midY, midX+1, currentTree.minY);
					}
					currentTree= currentTree.children[3];
				}
			}else{
				if(y> midY){
					if(currentTree.children[1] == null){
						currentTree.children[1]= new IntQuadTree(midX, currentTree.maxY,currentTree.minX, midY+1);
					}
					currentTree= currentTree.children[1];
				}else{
					if(currentTree.children[2] == null){
						currentTree.children[2]= new IntQuadTree(midX, midY, currentTree.minX, currentTree.minY);
					}
					currentTree= currentTree.children[2];
				}
			}
		}
		return true;
	}
	public Coordinated remove(Coordinated c){
		int[] coord= c.getCoord();
		return remove(coord[0],coord[1]);
	}
	
	public Coordinated remove(int x, int y){
		IntQuadTree currentTree= this, previousTree=null;
		Coordinated c=null;
		while(currentTree.o == null){
			int midX= (currentTree.maxX-currentTree.minX)/2 + currentTree.minX;
			int midY= (currentTree.maxY-minY)/2 + currentTree.minY;
			previousTree= currentTree;
			if(x> midX){
				if(y> midY){
					currentTree= currentTree.children[0];
				}else{
					currentTree= currentTree.children[3];
				}
			}else{
				if(y> midY){
					currentTree= currentTree.children[1];
				}else{
					currentTree= currentTree.children[2];
				}
			}
			if(currentTree==null){
				return null;
			}
		}
		int[] coord= currentTree.o.getCoord();
		if(coord[0]==x && coord[1]==y){
			c=currentTree.o;
			currentTree.o=null;
			if(!currentTree.isEmpty()){
				System.out.println("Something is fishy in the QuadTrees of space!");
			}
			
			int midX= (previousTree.maxX-previousTree.minX)/2 + previousTree.minX;
			int midY= (previousTree.maxY-minY)/2 + previousTree.minY;
			if(x> midX){
				if(y> midY){
					currentTree.children[0]=null;
				}else{
					currentTree.children[3]=null;
				}
			}else{
				if(y> midY){
					currentTree.children[1]=null;
				}else{
					currentTree.children[2]=null;
				}
			}
			
		}else{
			return null;
		}
		
		return c;
	}
	
	public Coordinated get(int x, int y){
		IntQuadTree currentTree= this;
		Coordinated c=null;
		while(currentTree.o == null){
			int midX= (currentTree.maxX-currentTree.minX)/2 + currentTree.minX;
			int midY= (currentTree.maxY-minY)/2 + currentTree.minY;
			if(x> midX){
				if(y> midY){
					currentTree= currentTree.children[0];
				}else{
					currentTree= currentTree.children[3];
				}
			}else{
				if(y> midY){
					currentTree= currentTree.children[1];
				}else{
					currentTree= currentTree.children[2];
				}
			}
			if(currentTree==null){
				return null;
			}
		}
		int[] coord= currentTree.o.getCoord();
		if(coord[0]!=x || coord[1]!=y){
			return null;
		}
		return currentTree.o;
	}
	
	public LinkedList<Coordinated> get(int maxX, int maxY, int minX, int minY){
		LinkedList<Coordinated> results= new LinkedList<Coordinated>();
		LinkedList<IntQuadTree> stack= new LinkedList<IntQuadTree>();
		IntQuadTree current;
		stack.add(this);
		while(!stack.isEmpty()){
			current= stack.poll();
			if(current.o != null){
				int[] coord= current.o.getCoord();
				if(coord[0]>= minX && coord[0]<= maxX && coord[1]>=minY && coord[1] <=maxY){
					results.add(current.o);
				}
			}
			for(int i=0; i<4; i++){
				IntQuadTree child= current.children[i];
				if(child != null && !(child.maxX<minX || child.minX>maxX || child.maxY<minY || child.minY>maxY)){
					stack.add(child);
				}
			}
		}

		return results;
	}
	
	public LinkedList<Coordinated> get(int x, int y, float r){
		int maxX= (int) (x+r) +1;
		int maxY= (int) (y+r) +1;
		int minX= (int) (x-r);
		int minY= (int) (x-r);
		float r2= r*r;
		LinkedList<Coordinated> results= new LinkedList<Coordinated>();
		LinkedList<IntQuadTree> stack= new LinkedList<IntQuadTree>();
		IntQuadTree current;
		stack.add(this);
		while(!stack.isEmpty()){
			current= stack.poll();
			if(current.o != null){
				int[] coord= current.o.getCoord();
				int x1= coord[0]-x;
				int y1= coord[1]-y;
				if(x1*x1 + y1*y1 < r2){
					results.add(current.o);
				}
			}
			for(int i=0; i<4; i++){
				IntQuadTree child= current.children[i];
				if(child != null && !(child.maxX<minX || child.minX>maxX || child.maxY<minY || child.minY>maxY)){
					stack.add(child);
				}
			}
		}

		return results;
	}
	
}
